package _back_tracking

import org.junit.Assert
import org.junit.Test

/**
 * https://leetcode.cn/problems/additive-number/description/?envType=problem-list-v2&envId=backtracking
 *
 * https://www.bilibili.com/video/BV15T4y1171f
 *
 * TODO:306. 累加数
 *
 * ```
 * 累加数 是一个字符串，组成它的数字可以形成累加序列。
 *
 * 一个有效的 累加序列 必须 至少 包含 3 个数。除了最开始的两个数以外，序列中的每个后续数字必须是它之前两个数字之和。
 *
 * 给你一个只包含数字 '0'-'9' 的字符串，编写一个算法来判断给定输入是否是 累加数 。如果是，返回 true ；否则，返回 false 。
 *
 * 说明：累加序列里的数，除数字 0 之外，不会 以 0 开头，所以不会出现 1, 2, 03 或者 1, 02, 3 的情况。
 *
 * 示例 1：
 * 输入："112358"
 * 输出：true
 * 解释：累加序列为: 1, 1, 2, 3, 5, 8 。1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8

 * 示例 2：
 * 输入："199100199"
 * 输出：true
 * 解释：累加序列为: 1, 99, 100, 199。1 + 99 = 100, 99 + 100 = 199
 *
 *
 * 提示：
 * 1 <= num.length <= 35
 * num 仅由数字（0 - 9）组成
 * ```
 *
 */
class leetcode_306 {

    @Test
    fun test_1() {
        val result = isAdditiveNumber("112358")
        val expected = true
        Assert.assertEquals(expected, result)
    }

    @Test
    fun test_2() {
        val result = isAdditiveNumber("199100199")
        val expected = true
        Assert.assertEquals(expected, result)
    }

    private fun isAdditiveNumber(num: String): Boolean {
        if (num.length < 3) {
            return false
        }
        return backtracking(num, 0)
    }

    val result: ArrayList<Long> = ArrayList()

    // 回溯
    // 1 确定函数的参数和返回值
    private fun backtracking(num: String, start: Int): Boolean {
        // 2 确定终止条件
        if (start >= num.length) {
            if (result.size < 3) {
                return false
            }
        }

        if (result.size >= 3) {
            // 收集结果
            if ((result[result.size - 3] + result[result.size - 2]) == result[result.size - 1]) {
                System.err.println("valid result=$result")
                return true
            }
            return false
        }
        // 3 单层循环
        for (i in start + 1 until num.length) {
            // 处理节点
            val s: String = num.substring(start until i)
//            System.err.println("s=$s")

            if (!isValid(s)) {
                return false
            }

            result.add(s.toLong())
            System.err.println("start=$start,i = $i, s=$s, result=$result")

            // 递归
            backtracking(num, i)

            // 回溯
            result.removeAt(result.size - 1)
        }
        return false
        // 4 剪枝
        // 5 去重
    }

    private fun isValid(s: String): Boolean {
        // 空？
        if (s.isEmpty()) {
            return false
        }

        // 以0 开头？
        if (s.length > 1 && s.substring(0 until 1) == "0") {
            return false
        }

        val chArray = s.toCharArray()
        // 0-9 ?
        for (i in 0 until chArray.size) {
            if (!isValid(chArray[i])) {
                return false
            }
        }
        return true
    }

    private fun isValid(ch: Char): Boolean {
        if ('0' <= ch && ch <= '9') {
            return true
        }
        return false
    }
}